Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

Trapping Rain Water - 图1

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Solution:

  1. public class Solution {
  2.   public int trap(int[] height) {
  3.     if (height == null || height.length == 0) {
  4.       return 0;
  5.     }
  7.     int n = height.length;
  8.     int max = 0;
  10.     // scan from left
  11.     int[] lmax = new int[n];
  12.     for (int i = 0; i < n; i++) {
  13.       lmax[i] = max;
  14.       max = Math.max(max, height[i]);
  15.     }
  17.     // scan from right
  18.     max = 0;
  19.     int[] rmax = new int[n];
  20.     for (int i = n - 1; i >= 0; i--) {
  21.       rmax[i] = max;
  22.       max = Math.max(max, height[i]);
  23.     }
  25.     // final scan
  26.     int res = 0;
  27.     for (int i = 0; i < n; i++) {
  28.       int water = Math.min(lmax[i], rmax[i]) - height[i];
  29.       res += water >= 0 ? water : 0;
  30.     }
  32.     return res;
  33.   }
  34. }